package rbtree;

import avl.AVLNode;

import static rbtree.RBTreeNode.BLACK;
import static rbtree.RBTreeNode.RED;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:咭咭熊
 * Date:2021 - 08 - 28
 * Time:15:50
 */

/***
 * 红黑树
 *1.红黑树的5个特点
 * (1)红黑树中的节点——红色或者黑色；
 * (2)红黑树中的根一定是黑色；
 * (3)红黑树的叶子节点一定是黑色的；
 * (4)红黑树中，任意路径（从根到叶子），红色和红色不能相邻；
 * (5)红黑树中，任意路径（从根到叶子），上面的黑色节点的数量一样多；
 *
 * 2.红黑树的插入规则：
 * （1）同普通搜索树的插入；
 * （2）判断是否破坏了红色与红色不能相邻的规则，若破坏了，需进行平衡调整；
 * （3）将根设置为黑色；
 */
public class RBTree {

    /***
     * 保存红黑树中的根节点
     */
    public RBTreeNode root = null;
    /***
     * 保存红黑树中的节点个数
     */
    public int size= 0;

    /***
     * 向红黑树中插入新的关键字
     * @param key 关键字
     * @return 返回是否插入成功
     * true——插入成功
     * false ——插入失败（key出现重复）
     */
    public boolean insert(long key){

        //1.按照普通搜索树的方式进行插入
        if (root == null){
            root = new RBTreeNode(key,null,BLACK);
            size++;
            return true;
        }

        RBTreeNode parent = null;
        RBTreeNode current =  root;
        while(current != null){
            if(key == current.key){
                return false;
            }else if(key < current.key){
                parent = current;
                current = current.left;
            }else{
                parent = current;
                current = current.right;
            }
        }
        /***
         * 根据插入规则——每次新插入的节点一定是红色的
         */
        RBTreeNode node = new RBTreeNode(key,parent, RED);
        if (key < parent.key) {
            parent.left = node;
        }else{
            parent.right = node;
        }
        size++;

        /***
         * 进行红黑树规则的判断+ 平衡调整过程
         */
        adjustBalance(node);
        return true;
    }

    /***
     * 平衡调整
     * @param node
     */
    private void adjustBalance(RBTreeNode node) {
        while(true){
            RBTreeNode parent = node.parent;
            if(parent == null){
                break;
            }

            if(parent.color == BLACK){
                break;
            }

            /***
             * 代码走到此处，说明一定屁哦坏了“红色与红色不能相邻”的规则
             */
            RBTreeNode grandpa = parent.parent;
            //找到叔叔节点
            if(parent == grandpa.left){
                RBTreeNode uncle = grandpa.right;
                /***情况1——uncle存在 && uncle的颜色是红色
                 * 调整步骤：
                 * （1）parent.color = BLACK;uncle.color = BLACK
                 *  (2)grandpa.color = RED
                 *  (3)将grandpa 视为node，重新循环进行再平衡过程，直到回溯到根为止；
                 */
                if(uncle != null && uncle.color == RED){
                    parent.color = BLACK;
                    uncle.color = BLACK;
                    grandpa.color = RED;
                    node = grandpa;
                    continue;
                }else{
                    //判断grandpa <-> parnet 和parent <-> node 的关系是否不一致
                    //已知 parent 是grandpa的左边
                    if(node == parent.right){
                        //左旋parent
                        leftRotate(parent);
                        //交换parent与node；原、node视为新的parent，原parent视为新的node
                        //swap(parent,node);
                        parent = node;
                    }

                    //接下来，统一处理关系一致的情况；
                    rightRotate(grandpa);
                    grandpa.color = RED;
                    parent.color = BLACK;
                    break;
                }
            }else{
                RBTreeNode uncle = grandpa.left;
                if(uncle != null && uncle.color == RED){
                    parent.color = BLACK;
                    uncle.color = BLACK;
                    grandpa.color = RED;
                    node = grandpa;
                    continue;
                }else{
                    //判断grandpa <-> parnet 和parent <-> node 的关系是否不一致
                    //已知 parent 是grandpa的右边
                    if(node == parent.left){
                        //左旋parent
                        rightRotate(parent);
                        //交换parent与node；原、node视为新的parent，原parent视为新的node
                        //swap(parent,node);
                        parent = node;
                    }
                    //接下来统一处理关系一致的情况
                    leftRotate(grandpa);
                    grandpa.color = RED;
                    parent.color = BLACK;
                    break;

                }
            }
        }
        /***
         * 代码走到此处，统一将将跟的颜色设置为黑色
         */
        root.color = BLACK;
    }

    /***
     * 以b节点进行左旋
     * @param b
     */
    private void  leftRotate(RBTreeNode b){

        //parent代表b节点可能存在的父节点
        RBTreeNode parent = b.parent;

        //图中的a节点
        RBTreeNode a = b.right;

        //leftOfRight代表图中的乙子树的根节点
        RBTreeNode leftOfRight = a.left;

        /***
         * 其中：m != null  && right != null
         * 但是parent 不能保证 ！null, leftOfRight 不保证 ！null
         */

        a.parent = parent;
        if(parent == null){
            //b == root
            root = a;
        }else{
            if(b == parent.left){
                parent.left = a;
            }else{
                parent.right = a;
            }
        }
        a.left = b;
        b.parent = a;

        b.right = leftOfRight;
        if(leftOfRight != null){
            leftOfRight.parent = b;
        }
    }
    /***
     * 以b节点进行右旋
     */

    private void rightRotate(RBTreeNode b){
        RBTreeNode parent = b.parent;
        RBTreeNode left = b.left;
        RBTreeNode rightOfLeft = left.right;

        left.parent = parent;
        if(parent == null){
            root = left;
        }else{
            if(b == parent.left){
                parent.left = left;
            }else{
                parent.right = left;
            }
        }
        left.right = b;
        b.parent = left;

        b.left = rightOfLeft;
        if(rightOfLeft  != null){
            rightOfLeft.parent = b;
        }
    }
}
